package someTestExcemple.huaweiOd.greedyMethod;

import java.util.Arrays;
import java.util.Scanner;

//华为OD机试 - 数字序列比大小 - 贪心思维（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/132524468
//要解决这个问题，我们可以采用贪心策略，即总是让A尽可能多地赢得比赛。
//为此，我们需要对A和B的数字序列进行排序。在每一轮比较中，如果B选择了一个数字，A会根据以下策略回应：
//如果A有比B当前选择的数字大的最小的数字，那么A就选择这个数字来赢得比赛。
//如果A没有能赢B当前数字的选项，A应该用自己的最小的数字去和B的数字对比，以减少损失。
//即尽可能让 A 用较小的数字去战胜 B 的较小数字，同时避免用 A 的大数字去输给 B 的小数字
public class NumberPickingGame {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        // 读取A和B的数字序列
        for(int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = scanner.nextInt();
        }
        scanner.close();
        System.out.println(maxPossibleScore(A,B));
    }

    private static int maxPossibleScore(int[] A, int[] B) {
        Arrays.sort(A);
        Arrays.sort(B);
        int aIndex = 0; // A的索引
        int bIndex = 0; // B的索引
        int score = 0;  // A的得分

        //先减枝
        //如果A最大的数字比B最小的数字还小，就全输了
        if(A[A.length-1] < B[0]) {
            return -A.length;
        }
        //必须要比较3次
        //todo 下面这种写法有问题，比如
        //输入
        //3
        //1 2 4
        //3 6 9
        //输出
        //-1
        // 遍历B的每个元素，找到A中可以赢B的最小元素
        /*while (bIndex < B.length) {
            if (A[aIndex] > B[bIndex]) {
                // A可以赢，加1分
                score++;
                bIndex++;  // B移动到下一个
            }
            aIndex++;  // 无论A赢或不赢，A都移动到下一个
            if (aIndex == A.length) break;  // A没有数字可用
        }*/
        int leftA = 0, rightA = A.length - 1;
        int leftB = 0, rightB = B.length - 1;
        //贪心思想，每一步做最优抉择
        //田忌赛马问题
//        贪心策略：
//        比较 A 和 B 的最大数字：
//        如果 A 的最大数字大于 B 的最大数字，A 用最大数字和 B 的最大数字比较，A 赢。
//        如果 A 的最大数字小于 B 的最大数字，A 用最小数字和 B 的最大数字比较，A 输。
//        如果 A 和 B 的最大数字相等，比较 A 和 B 的最小数字：
//        如果 A 的最小数字大于 B 的最小数字，A 用最小数字和 B 的最小数字比较，A 赢。
//        如果 A 的最小数字小于等于 B 的最小数字，A 用最小数字和 B 的最大数字比较。
        while (leftA <= rightA) {
            if (A[rightA] > B[rightB]) {
                // A 的最大数字大于 B 的最大数字，A 用最大数字和 B 的最大数字比较，A 赢
                score++;
                rightA--;
                rightB--;
                //不用再去比A的第二大数字和B的最大数字比较
                //因为如果A的第二大数字比B的最大数字大-则A第二大数字肯定比B第二大数字大
                //那么 A第二代数字和B第一大数字比，得1分，A第一代数字和B第二代数字比得1分
                //还是固定得两分
            } else if (A[rightA] < B[rightB]) {
                // A 的最大数字小于 B 的最大数字--这一局肯定要输
                //A 用最小数字和 B 的最大数字比较，A 输
                score--;
                leftA++;
                rightB--;
            } else {
                // A 和 B 的最大数字相等
                if (A[leftA] > B[leftB]) {
                    // A 的最小数字大于 B 的最小数字，A 用最小数字和 B 的最小数字比较，A 赢
                    score++;
                    leftA++;
                    leftB++;
                } else {
                    // A 的最小数字小于等于 B 的最小数字，A 用最小数字和 B 的最大数字比较
                    if (A[leftA] < B[rightB]) {
                        score--;
                    }
                    leftA++;
                    rightB--;
                }
            }
        }


        return score;
    }
}
